package com.tys.algorithm.advanced.code.class10;

import java.util.Stack;

/**
 * 非递归实现二叉树的遍历：先序、中序、后序
 */
public class Code03_UnRecursiveTraversalBT {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    //先序遍历：头左右
    public static void pre(Node head) {
        System.out.print("pre-order: ");
        if (head != null) {
            //准备栈
            Stack<Node> stack = new Stack<Node>();
            //压头
            stack.add(head);
            //栈为空结束
            while (!stack.isEmpty()) {
                //弹出头
                head = stack.pop();
                //打印弹出值
                System.out.print(head.value + " ");
                //先压右再压左
                //有右压右
                if (head.right != null) {
                    stack.push(head.right);
                }
                //有左压左
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    //中序遍历：左头右
    public static void in(Node cur) {
        System.out.print("in-order: ");
        if (cur != null) {
            Stack<Node> stack = new Stack<Node>();
            //栈为空，cur为空就停
            while (!stack.isEmpty() || cur != null) {
                //cur不为空则整条左边界都进栈
                if (cur != null) {
                    //头和左入栈
                    stack.push(cur);
                    //cur跳左
                    cur = cur.left;
                } else {
                    //cur为空就弹出栈顶
                    cur = stack.pop();
                    //打印弹出值
                    System.out.print(cur.value + " ");
                    //cur跳右孩子
                    cur = cur.right;
                }
            }
        }
        System.out.println();
    }

    //后续遍历左右头
    //方法1：使用2个栈，修改先序遍历的压栈顺序，先压左再压右
    //头左右-》头右左-》左右头
    public static void pos1(Node head) {
        System.out.print("pos-order: ");
        if (head != null) {
            //准备2个栈
            Stack<Node> s1 = new Stack<Node>();
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head); //压入头
            //s1栈为空结束
            while (!s1.isEmpty()) {
                //弹出栈顶
                head = s1.pop(); // 头 右 左
                //将s1栈顶压入s2：将头右左压栈
                s2.push(head);
                //先压左再压右
                //有左压左
                if (head.left != null) {
                    s1.push(head.left);
                }
                //有右压右
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            //弹出并打印s2栈中所有元素
            // 头右左从栈中弹出后变为左右头
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    //后续遍历左右头
    //方法2：使用1个栈
    public static void pos2(Node h) {
        System.out.print("pos-order: ");
        if (h != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                } else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                } else {
                    System.out.print(stack.pop().value + " ");
                    h = c;
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        pre(head);
        System.out.println("========");
        in(head);
        System.out.println("========");
        pos1(head);
        System.out.println("========");
        pos2(head);
        System.out.println("========");
    }

}
